{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Search in a Binary Search Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #binary-search-tree #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #二叉搜索树 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: searchBST"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #二叉搜索树中的搜索"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定二叉搜索树（BST）的根节点<meta charset=\"UTF-8\" />&nbsp;<code>root</code>&nbsp;和一个整数值<meta charset=\"UTF-8\" />&nbsp;<code>val</code>。</p>\n",
    "\n",
    "<p>你需要在 BST 中找到节点值等于&nbsp;<code>val</code>&nbsp;的节点。 返回以该节点为根的子树。 如果节点不存在，则返回<meta charset=\"UTF-8\" />&nbsp;<code>null</code>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/01/12/tree1.jpg\" style=\"height: 179px; width: 250px;\" /><meta charset=\"UTF-8\" /></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>root = [4,2,7,1,3], val = 2\n",
    "<b>输出：</b>[2,1,3]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/01/12/tree2.jpg\" style=\"height: 179px; width: 250px;\" />\n",
    "<pre>\n",
    "<b>输入：</b>root = [4,2,7,1,3], val = 5\n",
    "<b>输出：</b>[]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中节点数在&nbsp;<code>[1, 5000]</code>&nbsp;范围内</li>\n",
    "\t<li><code>1 &lt;= Node.val &lt;= 10<sup>7</sup></code></li>\n",
    "\t<li><code>root</code>&nbsp;是二叉搜索树</li>\n",
    "\t<li><code>1 &lt;= val &lt;= 10<sup>7</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [search-in-a-binary-search-tree](https://leetcode.cn/problems/search-in-a-binary-search-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [search-in-a-binary-search-tree](https://leetcode.cn/problems/search-in-a-binary-search-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[4,2,7,1,3]\\n2', '[4,2,7,1,3]\\n5']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:\n",
    "        if root is None:\n",
    "            return root\n",
    "        # find node\n",
    "        node = root\n",
    "        while node and node.val !=val:\n",
    "            if node.val>val:\n",
    "                node = node.left\n",
    "            else:\n",
    "                node = node.right\n",
    "        if node is None:\n",
    "            return None\n",
    "        else:\n",
    "            return node\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def searchBST(self, root: 'TreeNode', val: 'int') -> 'TreeNode':\n",
    "        if not root:\n",
    "            return None\n",
    "        if root.val==val:\n",
    "            return root\n",
    "        if root.val<val:\n",
    "            return self.searchBST(root.right,val)\n",
    "        if root.val>val:\n",
    "            return self.searchBST(root.left,val)\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def searchBST(self, root: 'TreeNode', val: 'int') -> 'TreeNode':\n",
    "        if not root:\n",
    "            return None\n",
    "        if root.val==val:\n",
    "            return root\n",
    "        if root.val!=val:\n",
    "            return self.searchBST(root.left,val) or self.searchBST(root.right,val)\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def searchBST(self, root, val):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :type val: int\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        while root:\n",
    "            if root.val == val:\n",
    "                return root\n",
    "            elif root.val > val:\n",
    "                root = root.left\n",
    "            else:\n",
    "                root = root.right\n",
    "        return None\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def searchBST(self, root, val):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :type val: int\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        if root is None:\n",
    "                return\n",
    "        list = []\n",
    "        #returnArr = []\n",
    "        while True:\n",
    "            if root.val == val:\n",
    "                return root\n",
    "            #returnArr.append(root.val)\n",
    "            print(root.val)\n",
    "            if root.right:\n",
    "                list.append(root.right)\n",
    "            if root.left:\n",
    "                root = root.left\n",
    "            elif len(list)>0:\n",
    "                root = list.pop()\n",
    "            else:\n",
    "                return\n",
    "        #return returnArr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def searchBST(self, root: TreeNode, val: int) -> TreeNode:\n",
    "        if not root:\n",
    "            return None\n",
    "        if root.val == val:\n",
    "            return root\n",
    "        else:\n",
    "            if root.val > val:\n",
    "                return self.searchBST(root.left,val)\n",
    "            else:\n",
    "                return self.searchBST(root.right,val)\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def searchBST(self, root: TreeNode, val: int) -> TreeNode:\n",
    "        if not root:\n",
    "            return None\n",
    "        if root.val==val:\n",
    "            return root\n",
    "        root.left = self.searchBST(root.left,val)\n",
    "        root.right = self.searchBST(root.right,val)\n",
    "        return root.left or root.right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def searchBST(self, root: TreeNode, val: int) -> TreeNode:\n",
    "        if not root or root.val == val:\n",
    "            return root\n",
    "        left = self.searchBST(root.left, val)\n",
    "        right = self.searchBST(root.right, val)\n",
    "        if left and left.val == val:\n",
    "            return left\n",
    "        if right and right.val == val:\n",
    "            return right \n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def searchBST(self, root: TreeNode, val: int) -> TreeNode:\n",
    "        if root == None:\n",
    "            return\n",
    "        if root.val > val:\n",
    "            return self.searchBST(root.left,val)\n",
    "        elif root.val < val:\n",
    "            return self.searchBST(root.right,val)\n",
    "        else:\n",
    "            return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def searchBST(self, root: TreeNode, val: int) -> TreeNode:\n",
    "        if root is None: return None\n",
    "        if root.val == val: return root\n",
    "        elif root.val > val: return self.searchBST(root.left, val)\n",
    "        return self.searchBST(root.right, val)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchBST(self, root: TreeNode, val: int) -> TreeNode:\n",
    "        stack = [root]\n",
    "\n",
    "        while stack:\n",
    "            node = stack.pop()\n",
    "            \n",
    "            if not node:\n",
    "                continue\n",
    "\n",
    "            if node.val == val:\n",
    "                return node\n",
    "\n",
    "            if node.val > val:\n",
    "                stack.append(node.left)\n",
    "            elif node.val < val:\n",
    "                stack.append(node.right)\n",
    "\n",
    "        return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def searchBST(self, root: TreeNode, val: int) -> TreeNode:\n",
    "        while root:\n",
    "            if val>root.val:\n",
    "                root=root.right\n",
    "            elif val<root.val:\n",
    "                root=root.left\n",
    "            elif root.val==val:\n",
    "                return root\n",
    "        return None\n",
    "    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def searchBST(self, root: TreeNode, val: int) -> TreeNode:\n",
    "        if not root:\n",
    "            return None\n",
    "        if root.val == val:\n",
    "            return root\n",
    "        if root.val > val and root.left:\n",
    "            return self.searchBST(root.left, val)\n",
    "        if root.val < val and root.right:\n",
    "            return self.searchBST(root.right, val)\n",
    "        return None\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def searchBST(self, root: TreeNode, val: int) -> TreeNode:  # 递归解法\n",
    "        if root is None:\n",
    "            return None\n",
    "        if val == root.val:\n",
    "            return root\n",
    "        elif val < root.val:\n",
    "            return self.searchBST(root.left, val)\n",
    "        else:\n",
    "            return self.searchBST(root.right, val)\n",
    "\n",
    "\n",
    "# class Solution: \n",
    "#     def searchBST(self, root: TreeNode, val: int) -> TreeNode:  # 非递归解法\n",
    "#         if root is None:\n",
    "#             return None\n",
    "#         while root:\n",
    "#             if val == root.val:\n",
    "#                 return root\n",
    "#             elif val < root.val:\n",
    "#                 root = root.left\n",
    "#             else:\n",
    "#                 root = root.right\n",
    "#         return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def searchBST(self, root: TreeNode, val: int) -> TreeNode:\n",
    "        if not root:\n",
    "            return None\n",
    "        while root:\n",
    "            if val>root.val:\n",
    "                root = root.right\n",
    "            elif val < root.val:\n",
    "                root = root.left\n",
    "            elif root.val == val:\n",
    "                return root\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def searchBST(self, root: TreeNode, val: int) -> TreeNode:\n",
    "        while root:\n",
    "            if root.val==val:\n",
    "                return root\n",
    "            elif root.val>val:\n",
    "                root=root.left\n",
    "            elif root.val<val:\n",
    "                root=root.right\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def searchBST(self, root: TreeNode, val: int) -> TreeNode:\n",
    "        # 递归\n",
    "        if not root or root.val == val:\n",
    "            return root\n",
    "        root.left = self.searchBST(root.left, val)\n",
    "        root.right = self.searchBST(root.right, val)\n",
    "        return root.left or root.right\n",
    "        # return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def searchBST(self, root: TreeNode, val: int) -> TreeNode:\n",
    "        p = root\n",
    "        while p:\n",
    "            if p.val < val:\n",
    "                p = p.right\n",
    "            elif p.val > val:\n",
    "                p = p.left\n",
    "            else:\n",
    "                return p\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def searchBST(self, root: TreeNode, val: int) -> TreeNode:\n",
    "        # 二叉搜索树的迭代\n",
    "        while root:\n",
    "            if root.val == val:\n",
    "                return root\n",
    "            elif root.val > val:\n",
    "                root = root.left\n",
    "            else:\n",
    "                root = root.right\n",
    "        return None\n",
    "\n",
    "        # 一提到二叉树遍历的迭代法，可能立刻想起使用 栈(stack) 来模拟深度遍历 DFS\n",
    "        # 使用队列(deque)来模拟广度遍历。\n",
    "\n",
    "        # 对于二叉搜索树可就不一样了，因为二叉搜索树的特殊性，也就是节点的有序性，可以不使用辅助栈或者队列\n",
    "        # 就可以写出迭代法。对于一般二叉树，递归过程中还有回溯的过程.\n",
    "\n",
    "        # 迭代\n",
    "        # if not root:\n",
    "        #     return None\n",
    "        # stack = [root]\n",
    "\n",
    "        # while stack:\n",
    "        #     cur = stack.pop()\n",
    "        #     if cur.val == val:\n",
    "        #         return cur\n",
    "        #     else:\n",
    "        #         if cur.right:\n",
    "        #             stack.append(cur.right)\n",
    "        #         if cur.left:\n",
    "        #             stack.append(cur.left)\n",
    "        # return None\n",
    "\n",
    "        # DFS\n",
    "        # if not root or root.val == val:\n",
    "        #     return root\n",
    "        # if root.val > val:\n",
    "        #     return self.searchBST(root.left,val)\n",
    "        # if root.val < val:\n",
    "        #     return self.searchBST(root.right,val)\n",
    "\n",
    "        # 层序遍历 BFS\n",
    "        # if not root:\n",
    "        #     return None\n",
    "        # que = collections.deque([root])\n",
    "\n",
    "        # while que:\n",
    "        #     n = len(que)\n",
    "        #     for _ in range(n):\n",
    "        #         cur = que.popleft()\n",
    "        #         if cur.val == val:\n",
    "        #             return cur\n",
    "        #         if cur.left:\n",
    "        #             que.append(cur.left)\n",
    "        #         if cur.right:\n",
    "        #             que.append(cur.right)\n",
    "        # return None\n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return None\n",
    "        \n",
    "        while root:\n",
    "            if root.val == val:\n",
    "                return root\n",
    "            elif root.val < val:\n",
    "                root = root.right\n",
    "            else:\n",
    "                root = root.left\n",
    "        \n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:\n",
    "        if root==None:\n",
    "            return None\n",
    "        if root.val == val:\n",
    "            return root\n",
    "        root.left = self.searchBST(root.left,val)\n",
    "        root.right = self.searchBST(root.right,val)\n",
    "        if root.left:\n",
    "            return root.left\n",
    "        if root.right:\n",
    "            return root.right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return None\n",
    "        \n",
    "        if root.val == val:\n",
    "            return root\n",
    "        \n",
    "        root.left = self.searchBST(root.left,val)\n",
    "        root.right = self.searchBST(root.right,val)\n",
    "\n",
    "        if root.left:\n",
    "            return root.left\n",
    "        if root.right:\n",
    "            return root.right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:\n",
    "        # res = []\n",
    "\n",
    "        def dfs(node):          \n",
    "            if node is None:\n",
    "                return\n",
    "\n",
    "            if node.val == val:\n",
    "                return node\n",
    "            if node.val < val:\n",
    "                r = dfs(node.right)\n",
    "                if r is not None:\n",
    "                    return r\n",
    "\n",
    "            if node.val > val:\n",
    "                l = dfs(node.left)\n",
    "                if l is not None:\n",
    "                    return l\n",
    "         \n",
    "        s = dfs(root)\n",
    "        print(s)\n",
    "        return s\n",
    "        # if s is not None:\n",
    "        #     return s\n",
    "        # else:\n",
    "        #     return None\n",
    "        # print(s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:\n",
    "        while root:\n",
    "            print(root)\n",
    "            if root.val == val:\n",
    "                return root\n",
    "            if root.val < val:\n",
    "                root = root.right\n",
    "            else:\n",
    "                root = root.left\n",
    "        return None\n",
    "        \n",
    "# class Solution:\n",
    "#     def searchBST(self, root: TreeNode, val: int) -> TreeNode:\n",
    "#         while root:\n",
    "#             if val == root.val:\n",
    "#                 return root\n",
    "#             root = root.left if val < root.val else root.right\n",
    "#         return None\n",
    "\n",
    "# 作者：LeetCode-Solution\n",
    "# 链接：https://leetcode.cn/problems/search-in-a-binary-search-tree/solution/er-cha-sou-suo-shu-zhong-de-sou-suo-by-l-d8zi/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:\n",
    "        def dfs(node):\n",
    "            if node == None:\n",
    "                return None\n",
    "            \n",
    "            if node.val == val:\n",
    "                return node\n",
    "            if val < node.val:\n",
    "                node.left = dfs(node.left)\n",
    "                return node.left\n",
    "            if val > node.val:\n",
    "                node.right = dfs(node.right)\n",
    "                return node.right\n",
    "        return dfs(root)\n",
    "        \n",
    "  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:\n",
    "        ret = None\n",
    "\n",
    "        def dfs(node):\n",
    "            nonlocal ret\n",
    "            if node is None: return\n",
    "            if node.val == val:\n",
    "                ret = node\n",
    "                return\n",
    "            dfs(node.left)\n",
    "            dfs(node.right)\n",
    "        \n",
    "        dfs(root)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "class Solution:\n",
    "    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:\n",
    "        if root==None:\n",
    "            return None\n",
    "        if val<root.val:\n",
    "            return self.searchBST(root.left,val)\n",
    "        if val>root.val:\n",
    "            return self.searchBST(root.right,val)\n",
    "        return root"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
